---
title: 数据结构
---
这里说的数据结构并不是 String(字符串)、List(列表)、Hash(哈希)、Set(集合)和 SortedSet(有序集合)，这些只是 Redis 键值对中值的数据类型，也就是数据的保存形式。

这里说的数据结构，是它们的底层实现。

简单来说，底层数据结构一共有 6 种，分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。它们和数据类型的对应关系如下图所示：

![](https://img.wkq.pub/pic/8219f7yy651e566d47cc9f661b399f01.webp)

String 类型的底层实现只有一种数据结构，简单动态字符串。

而 List 、Hash、Set、SortedSet 这四种数据类型，都有两种底层实现结构。通常情况下，我们会把这四种类型称为集合类型，它们的特点是**一个键对应了一个集合的数据**。

上面这些数据结构都是值得底层实现，所以：

1. 键和值本身之间用什么结构组织？
2. 为什么集合类型有这么多的底层结构，它们都是怎么组织数据的？
3. 什么是简单动态字符串？

## 键和值用什么结构组织

为了实现从键到值得快速访问，Redis 使用了一个 哈希表来保存所有键值对。

一个哈希表，就是就是一个数组，数组中的每一个元素称为一个哈希桶。每个哈希桶种保存了键值对数据。

:::tip 如果值是集合类型的话，作为数组元素的哈希桶怎么保存呢？

哈希桶中的元素保存的并不是值本身，而是指向具体值的指针。不管值是 String ，还是集合类型，哈希桶中的元素都是指向它们的指针。

:::

哈希桶中的entry 元素保存了 *key 和 *value 指针，分别指向了实际的键和值。这样一来，即使是一个集合，也可以通过 *value 指针被查到。

![](https://img.wkq.pub/pic/1cc8eaed5d1ca4e3cdbaa5a3d48dfb5f.webp)

因为这个哈希表保存了所有的键值对。所以，也把它称为**全局哈希表**。哈希表的最大好处就是可以让我们用 O(1)的时间按复杂度快速查找到键值对——我们只需要计算键的哈希值，就可以知道它所对应的哈希桶位置，然后就可以访问相应的 entry 元素。

这个查找过程主要依赖于哈希计算，和数据量的多少并没有直接关系。也就是说，不管哈希表里有 10万个键还是 100 万个键，都只需要一次计算就能找到相应的键。



当你往 Redis 中写入大量数据后，就可能发现操作有时候会突然变慢了。这其实是因为**哈希表的冲突问题和 rehash 可能带来的操作阻塞**。

当你往哈希表写入更多数据时，哈希冲突是不可避免地。这里的哈希冲突，指的是两个 key 的哈希值，正好落在了同一个哈希桶中。

哈希桶的个数通常少于 key 的数量，所以难免会有一些 key 的哈希值对应到了同一个哈希桶中。

Redis 解决哈希冲突的方式，就是链式哈希。链式哈希就是指**同一个哈希桶中的多个元素用多个链表来保存，它们之间依次用指针连接。**也叫做哈希冲突链。

![8ac4cc6cf94968a502161f85d072e428](https://img.wkq.pub/pic/8ac4cc6cf94968a502161f85d072e428.webp)

哈希冲突链上的元素只能通过指针逐一查找再操作。如果哈希表里写入的数据越来越多，哈希冲突也会越来越多，这就会导致某些哈希冲突链过长，进而导致这个链上的元素查找耗时。

所以，Redis 会对哈希表做 rehash 操作。rehash 也就是增加现有的哈希桶数量，让逐渐增多的 entry 元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从而减少单个桶中的冲突。

具体步骤如下：

Redis 默认使用了两个全局哈希表：哈希表1 和哈希表 2。一开始，当你刚插入数据时，默认使用哈希表1，此时哈希表2 并没有被分配空间。随着数据逐渐增多，Redis 开始执行 rehash，这个过程分为三步：

1. 给哈希表2 分配更大的空间，例如是当前哈希表1 大小的两倍；
2. 把哈希表1 中的数量重新映射并拷贝到哈希表2中；
3. 释放哈希表1 的空间。

到此，就可以从哈希表1 切换到哈希表2  ，用增大的哈希表2 保存更多数据，而原来的哈希表1 留作下一次 rehash 扩容备用。

这个过程第二步涉及拷贝大量的服务数据，如果一次性把哈希表 1 中的数据都迁移完，会造成 Redis 线程阻塞，无法服务其他请求。此时，Redis 就无法快速访问数据了。

所以，Redis 采用了**渐进式 rehash**

简单来说，就是第二部拷贝数据时，Redis 仍然正常处理客户端请求，每处理一个请求时，从哈希表1 中的第一个索引位置开始，顺带着将这个索引位置上的所有 entries 拷贝到哈希表 2 中；等处理下一个请求时，再顺带拷贝哈希表 1 中的下一个位置的 entries 。

![73fb212d0b0928d96a0d7d6ayy76da0c](https://img.wkq.pub/pic/73fb212d0b0928d96a0d7d6ayy76da0c.webp)

这样就巧妙地把一次性大量拷贝的开销，分摊到多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。

对于 String 类型来说，找到 哈希桶就能直接增删改查了，所以哈希表的 O(1) 操作复杂度也就是它的复杂度了。

但是，对于集合类型来说，即使找到哈希桶了，还要在集合中再进一步进行操作。

## 集合数据操作效率

和 String类型不同，一个集合类型的值，第一步是通过全局哈希表找到对应的桶位置，第二步是在集合中再增删改查。那么，集合的操作效率和那些因素相关呢？

首先，与集合的底层数据结构有关。例如，使用哈希表实现的集合，要比使用链表实现的集合访问效率更高。其次，操作效率和这些操作本身的执行特点有关，比如读写一个元素的操作要比读写所有元素的效率高。

### 底层数据结构

集合的底层数据结构主要有 5 种，整数数组、双向链表、哈希表、压缩列表和跳表。

其中，哈希表的操作特点上面已经说过了；整数数组和双向链表也和很常见，它们的操作特征都是顺序读写，也就是通过数组下标或者链表指针逐个元素访问，操作复杂度基本是 O(N),操作效率比较低；

压缩列表实际上是一个数组，数组中的每一个元素都对应保存一个数据。和数组不同的是，压缩列表在表头有三个字段 zlbytes、zltail、zllen、分别表示列表长度、列表尾的偏移量和列表中 entry 的个数；
压缩列表在表尾还有一个 zlend ，表示列表结束。

![](https://img.wkq.pub/pic/9587e483f6ea82f560ff10484aaca4a0.webp)

在压缩列表中，如果我们要查找定位第一个元素和最后一个元素，可以通过表头三个字段的长度直接定位，复杂度是 O(1) 。而查找其它元素时，就没有这么高效了，只能逐个查找，此时的复杂度就是 O(N) 了。

接下来看下跳表：

有序链表只能逐一查找元素，导致操作起来非常慢，于是就出现了跳表。

具体来说，跳表在链表的基础上，**增加了多级索引，通过索引位置的几个跳转，实现数据的快速定位。**如下图所示：

![1eca7135d38de2yy16681c2bbc4f3fb4](https://img.wkq.pub/pic/1eca7135d38de2yy16681c2bbc4f3fb4.webp)

如果我们要在链表中查找 33 这个元素，只能从头开始遍历链表，查找 6 次，直到找到 33 为止。此时，时间复杂度是 O(N),查找效率很低。

为了提高查询效率，增加一级索引：从第一个元素开始，每两个元素选一个出来作为索引。这些索引再通过指针指向原始的链表。例如，从前两个元素中抽取元素1 作为一级索引，从第三四个元素中抽取元素 11 作为 一级索引。此时，只需要查找 4 次就可以定位到元素 33 了。

如果还想更快，可以再增加二级索引：从一级索引中，再抽取部分元素作为二级索引。

可以看到，这个查找过程就是在多级索引上跳来跳去，最后定位到元素。当数据量很大的时候，跳表的时间复杂度是 O(logN)。

![](https://img.wkq.pub/pic/fb7e3612ddee8a0ea49b7c40673a0cf0.webp)

### 不同操作的复杂度

集合类型的操作类型很多，有读写单个集合元素的，例如 HGET、HSET、也有操作多个元素的，例如 SADD，还有对整个集合进行遍历操作的，例如 SMEMBERS。这么多操作，它们的复杂度也各不相同。而复杂度的高低又是我们选择集合类型的重要依据。

